package com.lw.leetcode.back.b;

/**
 * Created with IntelliJ IDEA.
 * 2018. 判断单词是否能放入填字游戏内
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/24 20:39
 */
public class PlaceWordInCrossword {

    public static void main(String[] args) {
        PlaceWordInCrossword test = new PlaceWordInCrossword();

        // true
//        char[][] board = {{'#', ' ', '#'}, {' ', ' ', '#'}, {'#', 'c', ' '}};
//        String word = "abc";

        // true
//        char[][] board = {{'c', ' ', '#'}, {'#', '#', '#'}};
//        String word = "ab";


        // true
        char[][] board = {{'#', ' ', '#'}, {'#', ' ', '#'}, {'#', ' ', 'c'}};
        String word = "ca";

        boolean b = test.placeWordInCrossword(board, word);
        System.out.println(b);

    }

    public boolean placeWordInCrossword(char[][] board, String word) {
        char[] chars = word.toCharArray();
        boolean b = find(board, chars);
        if (b) {
            return b;
        }
        int length = chars.length;
        int l = length >> 1;
        for (int i = 0; i < l; i++) {
            char c = chars[i];
            chars[i] = chars[length - i - 1];
            chars[length - i - 1] = c;
        }
        return find(board, chars);
    }

    private boolean find (char[][] board, char[] items) {
        int m = board.length;
        int n = board[0].length;
        int length = items.length;
        int l = n - length;
        for (int i = 0; i < m; i++) {
            char[] arr = board[i];
            for (int j = 0; j <= l; j++) {
                if (j == 0 || arr[j - 1] == '#') {
                    int index = 0;
                    for (; j < n && index < length; j++) {
                        if (arr[j] == ' ' || arr[j] == items[index]) {
                            index++;
                        } else {
                            break;
                        }
                    }
                    if (index == length && (j == n || arr[j] == '#')) {
                        return true;
                    }
                }

            }
        }

        l = m - length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= l; j++) {
                if (j == 0 || board[j - 1][i] == '#') {
                    int index = 0;
                    for (; j < m && index < length; j++) {
                        if (board[j][i] == ' ' || board[j][i] == items[index]) {
                            index++;
                        } else {
                            break;
                        }
                    }
                    if (index == length && (j == m || board[j][i] == '#')) {
                        return true;
                    }
                }
            }
        }
        return false;
    }


}
